package main

import "fmt"

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	m := len(obstacleGrid)
	n := len(obstacleGrid[0])
	if obstacleGrid[0][0] == 1 {
		return 0
	}
	if m == 1 && n == 1 {
		if obstacleGrid[0][0] == 1 {
			return 0
		} else {
			return 1
		}
	}
	// 初始化最顶上一行，最左侧一列
	// 并将障碍设置为-1
	basicData := 1
	// fmt.Println(obstacleGrid)
	for i := 1; i < m; i++ {
		if obstacleGrid[i][0] == 1 {
			basicData = -1
			obstacleGrid[i][0] = basicData
		} else {
			obstacleGrid[i][0] = basicData
		}
	}
	// fmt.Println(obstacleGrid)
	basicData = 1
	for i := 1; i < n; i++ {
		if obstacleGrid[0][i] == 1 {
			basicData = -1
			obstacleGrid[0][i] = basicData
		} else {
			obstacleGrid[0][i] = basicData
		}
	}
	// fmt.Println(obstacleGrid)
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			obstacleGrid[i][j] = getValue(obstacleGrid, i, j)
		}
	}
	// fmt.Println(obstacleGrid)
	if obstacleGrid[m-1][n-1] == -1 {
		return 0
	} else {
		return obstacleGrid[m-1][n-1]
	}
}

func getValue(arr2 [][]int, i int, j int) int {
	if arr2[i][j] == 1 {
		return -1
	} else if arr2[i-1][j] == -1 && arr2[i][j-1] == -1 {
		return -1
	} else if arr2[i-1][j] == -1 {
		return arr2[i][j-1]
	} else if arr2[i][j-1] == -1 {
		return arr2[i-1][j]
	} else {
		return arr2[i-1][j] + arr2[i][j-1]
	}
}

func main() {
	input := [][]int{{0, 1}, {0, 0}}
	fmt.Println(uniquePathsWithObstacles(input))
	input = [][]int{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}
	fmt.Println(uniquePathsWithObstacles(input))
	input = [][]int{{0, 1, 0}}
	fmt.Println(uniquePathsWithObstacles(input))
}
